package com.leetcode.sorts.back_track;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: WuPeng
 * @Date: 2021/6/15 7:09 下午
 *
 * 216.组合总和3
 *
 */
public class CombinationSum3_216 {

    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> queue = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }

    private void backTracking(int k, int n, int index) {
        if (queue.size() == k && sum == n){
            result.add(new ArrayList<>(queue));
            return;
        }
        for (int j = index; j <= 9; j++) {
            sum += j;
            queue.offer(j);
            backTracking(k, n, j+1);
            queue.pollLast();
            sum -= j;
        }
    }

}
